/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/rotate-array
   @Language: C++
   @Datetime: 20-01-03 17:01
   */

// Method 1, Time O(2n), Space O(1)
class Solution {
	public:
	void rotate(vector<int>& nums, int k) {
		k=nums.size()-k%nums.size();
		if(k==0) return;
		reverse(nums.begin(), nums.begin()+k);
		reverse(nums.begin()+k, nums.end());
		reverse(nums.begin(), nums.end());
	}
};

// Method 2, Time O(n), Space O(1)
class Solution {
	public:
	void rotate(vector<int>& nums, int k) {
		int n=nums.size();
		k=k%n;
		if(k==0) return;
		for(int i=0, count=0; count<n; ++i){
			int j=i, tmp=nums[i];
			do{
				j=(j+k)%n;
				swap(tmp, nums[j]);
				++count;
			}while(i!=j);
		}
	}
};
